package com.demo.study.algorithm.sorts;


import static com.demo.study.utils.ArrayUtil.*;
import static com.demo.study.utils.ArrayUtil.printArray;

/**
 * 快速排序-单边循环
 *
 * @author Baymax
 * @since 2024-08-16
 */
public class B07_QuickSort {
    public static void main(String[] args) {
        int[] nums = intRandomArray();
        printArray(nums);
        lomutoQuickSort(nums);
        printArray(nums);
    }

    /**
     * 快速排序-罗穆托分区方案：单边快排(i和j都从左边开始)<p>
     * 核心思想：每轮找到一个基准点元素，把比它小的放到它的左边，比它大的放到它的右边，这称之为分区
     * <li>选择最右边元素作为基准点元素</li>
     * <li>j指针负责找到比基准点小的元素，一旦找到则与i交换</li>
     * <li>i指针指向大于基准点元素的左边界，也是每次交换的目标索引</li>
     * <li>最后基准点与i交换，i即为分区位置</li>
     */
    public static void lomutoQuickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(array, left, right); // p代表基准点元素的索引
        quick(array, left, p - 1);
        quick(array, p + 1, right);
    }

    private static int partition(int[] array, int left, int right) {
        int pv = array[right];
        int j = left;
        int i = left;
        while (j <= right) {
            if (array[j] < pv) {
                if (i != j) {
                    swap(array, i, j);
                }
                i++;
            }
            j++;
        }
        if (i != right) {
            swap(array, i, right);
        }
        return i;
    }

}
